// 跳跃游戏

package Leetcode;

class solution_045 {
    // DFS超出时间限制
    // public int minstep = Integer.MAX_VALUE;

    // public int jump(int[] nums) {
    // int steps = 0;
    // int currentlocation = 0;
    // dfs(nums, steps, currentlocation);
    // return minstep;
    // }

    // public void dfs(int[] nums, int steps, int currentlocation) {
    // if (steps > minstep)
    // return;
    // if (currentlocation == nums.length - 1)
    // minstep = minstep > steps ? steps : minstep;
    // if (currentlocation > nums.length - 1)
    // return;
    // if (currentlocation < nums.length - 1) {
    // for (int i = nums[currentlocation]; i > 0; i--) {
    // dfs(nums, steps + 1, currentlocation + i);
    // }
    // }
    // }

    // public static void main(String[] args) {
    // int[] nums = new int[] { 2, 3, 1, 1, 4 };
    // System.out.println(jump(nums));
    // }

    // 尝试使用DP算法
    public int jump(int[] nums) {
        // dp[i] 表示到达i位置的最小步数
        if (nums.length <= 1)
            return 0;
        int[] dp = new int[nums.length];
        dp[0] = 0;
        for (int i = 1; i < nums.length; i++) {
            dp[i] = Integer.MAX_VALUE;
            for (int j = 0; j < i; j++) {
                if (j + nums[j] >= i)
                    dp[i] = dp[j] + 1 < dp[i] ? dp[j] + 1 : dp[i];
            }
        }
        return dp[nums.length - 1];
    }
}

public class Solution045 {
    // 题解采用贪心算法，正向传播每次选择能走的最远的位置。
    public int jump(int[] nums) {
        int step = 0; // 步数，当到达边界bound时步数+1
        int bound = 0; // 边界，表示第i步所在位置所能达到的所有位置
        int maxPosition = 0; // 在边界范围内的值所能到达的最大位置
        for (int i = 0; i < nums.length - 1; i++) {
            // 在边界范围内值能到达最远的位置
            maxPosition = Math.max(maxPosition, i + nums[i]);
            if(i == bound ){ // 到达边界
                bound = maxPosition; // 更新边界
                step++; // 步数加一
            }
        }
        return step;
    }
}
